import heapq


class Solution(object):
    def smallestChair(self, times, targetFriend):
        times = [[t, v, index] for index, (t, v) in enumerate(times)]
        times.sort()
        n = len(times)
        un_schedule = [i for i in range(n)]
        schdule = []
        for t, v, index in times:
            while schdule and schdule[0][0] <= t:
                node = heapq.heappop(schdule)
                heapq.heappush(un_schedule, node[1])
            now = heapq.heappop(un_schedule)
            if index == targetFriend:
                return now
            else:
                heapq.heappush(schdule, [v, now])


data = Solution()
times = [[33889, 98676], [80071, 89737], [44118, 52565], [52992, 84310], [78492, 88209], [21695, 67063], [84622, 95452],
         [98048, 98856], [98411, 99433], [55333, 56548], [65375, 88566], [55011, 62821], [48548, 48656], [87396, 94825],
         [55273, 81868], [75629, 91467]]
targetFriend = 6
print(data.smallestChair(times, targetFriend))
